package 程序员面试金典;

import java.util.*;

public class 单词转换 {

    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue = new LinkedList<>();
        List<String> list = new ArrayList<>();
        boolean[] booleans = new boolean[wordList.size()];
        //存放单词的前驱
        Map<String, String> map = new HashMap<>();
        if (!wordList.contains(endWord))
            return list;
        boolean flag = false;
        queue.add(beginWord);
        while (queue.size()!=0){
            String poll = queue.poll();
            if (poll.equals(endWord)){
                flag=true;
                break;
            }
            //添加合适的单词到队列中
            for (int i = 0; i < wordList.size(); i++) {
                if (!booleans[i] && compare(poll,wordList.get(i))){
                      queue.add(wordList.get(i));
                      booleans[i]=true;
                      map.put(wordList.get(i),poll);
                }
            }
        }
        if (!flag)
            return list;
        String key=endWord;
        while (map.get(key)!=beginWord){
            list.add(key);
            key=map.get(key);
        }
        list.add(key);
        list.add(map.get(key));
        Collections.reverse(list);
        return list;
    }
    //判断两个单词相差的字符个数
    public boolean compare(String s1,String s2){
        int count=0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i)!=s2.charAt(i)) {
                count++;
                if (count>=2)
                    return false;
            }
        }
        return true;
    }
}
